package com.ly.algorithm.leetcode.dp;

/**
 * @Classname Problem5
 * @Description
 *
 * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
 *
 * 示例 1：
 *
 * 输入: "babad"
 * 输出: "bab"
 * 注意: "aba" 也是一个有效答案。
 * 示例 2：
 *
 * 输入: "cbbd"
 * 输出: "bb"
 *
 *
 * @Date 2020/12/23 16:23
 * @Author 冷心影翼
 */
public class Problem5 {

	public static void main(String[] args) {
		Solution5 solution5 = new Solution5();
		System.out.println(solution5.longestPalindrome("aa"));
	}

}


class Solution5 {
	public String longestPalindrome(String s) {
		if(s.length()==0)
			return "";
		boolean[][] dp = new boolean[s.length()][s.length()];
		String res = s.charAt(0)+"";
		for(int j=0;j<s.length();j++) {
			for(int i=0;i<j;i++) {
				if(s.charAt(i) != s.charAt(j))
					dp[i][j] = false;
				else {
					if(j-i<3)
						dp[i][j] = true;
					else
						dp[i][j] = dp[i+1][j-1];
				}

				if(dp[i][j] && j-i+1>res.length())
					res = s.substring(i,j+1);
			}
		}
		return res;
	}
}